The present disclosure generally relates to location based services and, in particular, to identifying points of interest that may be reached within a particular period of time.
Location based services are often used to find directions from one point of interest (POI) to another or to find the distance from one POI to another. However, in some applications, it may be helpful to identify an area (e.g., a set of destinations) that may be reached from a starting point during a fixed period of time (e.g., an allotted travel time). For example, a business or organization may need to decide where to place a new store or office. In making the decision of which location to place the new store or office, it may be useful to find out what area the new location will be able to serve (e.g., people living in a certain area will be able to reach the new location in 30 minutes or less). In another example, a business may need to determine where to send advertisements for an existing store or office. The business may determine that they will only target advertisements to people that may be within an hour drive of one of the business's locations. Other users may find the information helpful in figuring out which locations are convenient to visit.
The set of destinations that may be reached from a starting point within a predetermined time may be determined by using a brute force method to find all locations on a map that may be reached from the starting point within the predetermined time. However, the algorithms used to identify the locations typically require significant computing resources and processing time (e.g., the algorithms may have a time complexity of O(n2)) to determine the area. As a result, an increase in size of the map, an increase in the complexity of the map, or an increase in the allotted travel time causes a very large increase in the computing resources and processing time needed to identify the area.